/*
 * @lc app=leetcode.cn id=131 lang=cpp
 *
 * [131] 分割回文串
 *
 * https://leetcode-cn.com/problems/palindrome-partitioning/description/
 *
 * algorithms
 * Medium (72.80%)
 * Likes:    1108
 * Dislikes: 0
 * Total Accepted:    188.4K
 * Total Submissions: 258.7K
 * Testcase Example:  '"aab"'
 *
 * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
 * 
 * 回文串 是正着读和反着读都一样的字符串。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：s = "aab"
 * 输出：[["a","a","b"],["aa","b"]]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：s = "a"
 * 输出：[["a"]]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 
 * s 仅由小写英文字母组成
 * 
 * 
 */

// @lc code=start
class Solution {
// private:
//     vector<string> path;
//     vector<vector<string>> res;
//     bool isPalindrome(string str, int start, int end) {
//         // 判断的时候是一个 左闭右毕 的区间
//         for (int i = start, j = end; i < j; i++, j--) {
//             if(str[i] != str[j]) return false;
//         }
//         return true;
//     }

//     void backtracking(string str, int startIndex) {
//         if(startIndex == str.size()) {
//             res.push_back(path);
//             return;
//         }

//         for(int i = startIndex; i < str.size(); i++) {
//             if(isPalindrome(str, startIndex, i)) {
//                 // 此处判断左闭右毕区间的字符串是否是回文串，
//                 // 但是在截取字符串的时候，右闭区间的边界是少一个的
//                 string subStr = str.substr(startIndex, i - startIndex + 1);
//                 path.push_back(subStr);
//             } else {
//                 continue;
//             }
//             backtracking(str, i + 1);

//             path.pop_back();
//         }
//     }
// public:
//     vector<vector<string>> partition(string s) {
//         path.clear();
//         res.clear();
//         backtracking(s, 0);
//         return res;
//     }

// 复盘
private:
    vector<string> path;
    vector<vector<string>> res;
    void backtracking(string s, int startIndex) {
        if(s.size() == startIndex) {
            res.push_back(path);
            return;
        }

        for(int i = startIndex; i < s.size(); i++) {
            if(isValid(s, startIndex, i)) {
                string strSub = s.substr(startIndex, i - startIndex + 1);
                path.push_back(strSub);
                backtracking(s, i + 1);
                path.pop_back();
            } else continue;
        }
    }
    bool isValid(string str, int start, int end) {
        for(int i = start, j = end; i < j; i++, j--) {
            if(str[i] != str[j]) return false;
        }
        return true;
    }
public:
    vector<vector<string>> partition(string s) {
        path.clear();
        res.clear();
        backtracking(s, 0);
        return res;
    }

};
// @lc code=end

